Skip to main content

Maximum Product Subarray

Question​

What is the maximum product of any contiguous subarray of a given array of integers?

Example 1
Input: nums = [2, 3, -2, 4]
Output: 6 (maximum product subarray is [2, 3] which gives product of 6)

Solution​

all//Maximum Product Subarray.py


def maxProduct(arr, n):

    max_so_far = 0
    curr_max = 1
    curr_min = 1

    for i in range(n):

        if arr[i] > 0:
            curr_max = curr_max * arr[i]
            curr_min = min(curr_min * arr[i], 1)
        elif arr[i] == 0:
            curr_max = 1
            curr_min = 1
        else:
            temp = curr_max
            curr_max = max(curr_min * arr[i], 1)
            curr_min = temp * arr[i]

        max_so_far = max(max_so_far, curr_max)

    return max_so_far

arr = [6, -3, -10, 0, 2]
n = len(arr)
print(maxProduct(arr, n))